Search Results

Documents authored by Portier, Natacha

Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2014
LIPIcs, Volume 25, STACS'14, Complete Volume

Authors: Ernst W. Mayr and Natacha Portier

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
LIPIcs, Volume 25, STACS'14, Complete Volume
Cite as

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{mayr_et_al:LIPIcs.STACS.2014,
  title =	{{LIPIcs, Volume 25, STACS'14, Complete Volume}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014},
  URN =		{urn:nbn:de:0030-drops-45104},
  doi =		{10.4230/LIPIcs.STACS.2014},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2014.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Ernst W. Mayr and Natacha Portier

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. i-xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{mayr_et_al:LIPIcs.STACS.2014.i,
  author =	{Mayr, Ernst W. and Portier, Natacha},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{i--xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.i},
  URN =		{urn:nbn:de:0030-drops-44435},
  doi =		{10.4230/LIPIcs.STACS.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2013
LIPIcs, Volume 20, STACS'13, Complete Volume

Authors: Natacha Portier and Thomas Wilke

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
LIPIcs, Volume 20, STACS'13, Complete Volume
Cite as

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{portier_et_al:LIPIcs.STACS.2013,
  title =	{{LIPIcs, Volume 20, STACS'13, Complete Volume}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013},
  URN =		{urn:nbn:de:0030-drops-41144},
  doi =		{10.4230/LIPIcs.STACS.2013},
  annote =	{Keywords: Models of Computation, Nonnumerical Algorithms and Problems, Mathematical Logic, Formal Languages, Combinatorics, Graph Theory}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2013.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Natacha Portier and Thomas Wilke

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Frontmatter, Table of Contents, Preface, Workshop Organization
Cite as

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. i-xvii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{portier_et_al:LIPIcs.STACS.2013.i,
  author =	{Portier, Natacha and Wilke, Thomas},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{i--xvii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.i},
  URN =		{urn:nbn:de:0030-drops-39135},
  doi =		{10.4230/LIPIcs.STACS.2013.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.646
Author Index

Authors: Natacha Portier and Thomas Wilke

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Author Index.
Cite as

Natacha Portier and Thomas Wilke. Author Index. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 646-647, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{portier_et_al:LIPIcs.STACS.2013.646,
  author =	{Portier, Natacha and Wilke, Thomas},
  title =	{{Author Index}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{646--647},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.646},
  URN =		{urn:nbn:de:0030-drops-39729},
  doi =		{10.4230/LIPIcs.STACS.2013.646},
  annote =	{Keywords: Author Index}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.127
The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent

Authors: Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real tau-conjecture" which is inspired by this connection. The real tau-conjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial. In this paper we show that the real tau-conjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.
Cite as

Bruno Grenet, Pascal Koiran, Natacha Portier, and Yann Strozecki. The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 127-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.FSTTCS.2011.127,
  author =	{Grenet, Bruno and Koiran, Pascal and Portier, Natacha and Strozecki, Yann},
  title =	{{The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{127--139},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.127},
  URN =		{urn:nbn:de:0030-drops-33501},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.127},
  annote =	{Keywords: Algebraic Complexity, Sparse Polynomials, Descartes' Rule of Signs, Lower Bound for the Permanent, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.543
Symmetric Determinantal Representation of Weakly-Skew Circuits

Authors: Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.
Cite as

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.STACS.2011.543,
  author =	{Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
  title =	{{Symmetric Determinantal Representation of Weakly-Skew Circuits}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{543--554},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.543},
  URN =		{urn:nbn:de:0030-drops-30426},
  doi =		{10.4230/LIPIcs.STACS.2011.543},
  annote =	{Keywords: algebraic complexity, determinant and permanent of symmetric matrices, formulas, skew circuits, Valiant’s classes}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact